// K&R C3 p51

#include <stdio.h>

#define LEN 10

void shellsort(int v[], int n);

int main()
{
    int vv[LEN];
    int i;

    for (i = 0; i < LEN; i++)
        scanf("%d", &vv[i]);
    for (i = 0; i < LEN; i++)
        printf("OLD NO.%2d:\t%d\n", i, vv[i]);

    shellsort(vv, LEN);

    for (i = 0; i < LEN; i++)
        printf("NO.%2d:\t%d\n", i, vv[i]);

    return 0;
}

void shellsort(int v[], int n)
{
    int gap, i, j, temp;

    for (gap = n / 2; gap > 0; gap /= 2)
        for (i = gap; i < n; i++)
            for (j = i - gap; j >= 0 && v[j] > v[j + gap]; j -= gap)
            {
                temp = v[j];
                v[j] = v[j + gap];
                v[j + gap] = temp;
            }
}
